Leetcode刷题记录(Java)

发表于 | 更新于: | 分类于
Problem 558 Quad Tree Intersection/Problem 572 Subtree of Another Tree

Problem 558 Quad Tree Intersection
nziNLQ.png
该题比较有意思,给定的两棵树都是四叉树,需要求出两棵树相交后的新树,相交的原则是叶子结点的值做或运算.

主要思路:
直接对两个四叉树的结点进行比较,并对结点进行或运算,这里需要注意如果四个叶子结点的值相同需要重新合成一个叶子结点.

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
// Definition for a QuadTree node.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    public Node() {}

    public Node(boolean _val,boolean _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/
class Solution {
    public Node intersect(Node quadTree1, Node quadTree2) {
        if(quadTree1 == null || quadTree2 == null) return null;
        
        if(quadTree1.isLeaf && quadTree2.isLeaf) {
            return new Node(quadTree1.val || quadTree2.val, true, null, null, null, null);
        } else if(quadTree1.isLeaf) {
            return quadTree1.val ? quadTree1 : quadTree2;
        } else if(quadTree2.isLeaf) {
            return quadTree2.val ? quadTree2 : quadTree1;
        } else {
            Node nTL = intersect(quadTree1.topLeft, quadTree2.topLeft);
            Node nTR = intersect(quadTree1.topRight, quadTree2.topRight);
            Node nBL = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
            Node nBR = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
            
            if(nTL.isLeaf && nTR.isLeaf && nBL.isLeaf && nBR.isLeaf) {
                if(nTL.val == nTR.val && nTR.val == nBL.val && nBL.val == nBR.val) {
                    return new Node(nTL.val, true, null, null, null, null);
                }
            }
            return new Node(false, false, nTL, nTR, nBL, nBR);
        }
    }
}

代码说明:
函数开始就是对两棵树进行判断,有任何一方为空则其交集为空.之后就是判断当前结点是否为叶子结点,如果两个都是则返回两者或运算之后的新结点.之后如果树1当前结点为叶子结点,则判断其是否为True,因为此时树2结点肯定不是叶子结点,而True和任何值做或操作都是True,所以返回其本身即可.下一步同理.剩下的情况就是树1和树2当前结点都不是叶子结点,这样就需要分别比较其四个孩子结点的关系,如果全部进行或运算后发现四个值都是叶子结点且值相同的话,则将四个结点合并成一个结点.

Problem 572 Subtree of Another Tree
nzVJbD.png
判断给定的一个树是否是另外一棵树的子树,子树的定义是树的结构和值与原树的部分或全部完全相同

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s == null) 
            return false;
        if(sameTree(s, t)){
            return true;
        }else{
            boolean left = isSubtree(s.left, t);
            boolean right = isSubtree(s.right, t);
            return left || right;
        }
    }
    private boolean sameTree(TreeNode node1, TreeNode node2){
        if(node1 != null && node2 != null){
            if(node1.val == node2.val){
                boolean left = sameTree(node1.left, node2.left); 
                boolean right = sameTree(node1.right, node2.right);
                return left && right;
            }else{
                return false;
            }
        }else{
            if(node1 == null && node2 == null){
                return true;
            }
            return false; 
        }
    }
}

代码说明:
由于题目说明自身也是自身的子树,所以需要在最开始比较两棵树是否完全相同.之后就对其左右子树分别进行判断